At EUROCRYPT 2011, Gentry and Halevi implemented a variant of Gentry's fullyhomomorphic encryption scheme. The core part in their key generation is togenerate an odd-determinant ideal lattice having a particular type of HermiteNormal Form. However, they did not give a rigorous proof for the correctness.We present a better key generation algorithm, improving their algorithm fromtwo aspects. -We show how to deterministically generate ideal lattices with odddeterminant, thus increasing the success probability close to 1. -We give a rigorous proof for the correctness. To be more specific, wepresent a simpler condition for checking whether the ideal lattice has thedesired Hermite Normal Form. Furthermore, our condition can be checked moreefficiently. As a result, our key generation is about 1.5 times faster. We also giveexperimental results supporting our claims. Our optimizations are based on theproperties of ideal lattices, which might be of independent interests.
展开▼
